package com.sh.sort;

import java.util.Arrays;

/**
 * @ClassName CountSort
 * @Description 技术排序
         * 思想：一个数组arr，，肯定在0-最大数之间max的数组maxArr，所以新建一个数组长度是max的数组，遍历arr，如果maxArr[arr[i]]==0,给赋值1，不等于就++
 *              遍历maxArr,如果大于0就循环它，赋值到result中，需要一个index来控制指针
 * @Author yaoqiang
 * @Date 2020/11/20 13:38
 * @Version 1.0
 */
public class CountSortDemo {
    public static void main(String[] args) {
        int[] arr={10,1,18,30,23,12,7,5,18,17};
        int[] result=countSort(arr);
        System.out.println(Arrays.toString(result));
    }

    private static int[] countSort(int[] arr) {
        int[] firstArray=new int[100];
        int[] lastArray=new int[arr.length];
        //得到最大的数，比如80，那就新建一个100的数组，循环arr,把first[arr[i]]的值设置成1，
        //第二次，循环firstArray，如果值=1就放入lastArray，设置临时变量来充当指针
        for (int i=0;i<arr.length;i++){
            if (firstArray[arr[i]]==0){
                firstArray[arr[i]]=1;
            }else {
                firstArray[arr[i]]+=1;
            }
        }
        int index=0;
        for (int i=0;i<firstArray.length;i++ ){
            if (firstArray[i]>0){
                for (int j=0;j<firstArray[i];j++){
                    lastArray[index]=i;
                    index++;
                }
            }
        }

        return lastArray;
    }

}
